package TOP101;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

/**
 * @Question BM27
 * @Date 2022/11/9 16:40
 * @Solution
 */
public class BM27 {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (pRoot == null) {
            return ans;
        }
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.add(pRoot);
        int t = 1; //奇数先加头 偶数先加尾
        while (!deque.isEmpty()) {
            int s = deque.size();
            ArrayList<Integer> row = new ArrayList<>();
            for (int i = 0; i < s; i++) {
                TreeNode cur = deque.getFirst();
                deque.removeFirst();
                row.add(cur.val);
                if (cur.left != null) {
                    deque.add(cur.left);
                }
                if (cur.right != null) {
                    deque.add(cur.right);
                }
            }
            if (t % 2 == 0) {
                row = reverse(row);
            }
            ans.add(row);
            t++;
        }
        return ans;
    }
    public static ArrayList<Integer> reverse(ArrayList<Integer> row) {
        ArrayList<Integer> res = new ArrayList<>();
        int s = row.size();
        for (int i = s - 1; i >= 0; i--) {
            res.add(row.get(i));
        }
        return res;
    }
}
